A sequence of symbols, wherein the symbols are chosen from an alphabet or a symbol set, can be compressed by entropy coding. An entropy coding engine assigns codewords for symbols based on the statistical model, i.e., the probability distributions of symbols. In general, more frequently used symbols are entropy coded with fewer bits and less frequently occurring symbols are entropy coded with more bits.
Entropy coding has been studied for decades. Basically, there are three types of entropy coding methods: variable length coding (VLC), like Huffman coding, arithmetic coding, and dictionary-based compression, like Lempel-Ziv (LZ) compression or Lempel-Ziv-Welch (LZW) compression.
The VLC codes use integer number of bits to represent each symbol. Huffman coding is the most widely used VLC method. It assigns fewer bits to a symbol with greater probability, while assigning more bits to a symbol with a smaller probability. Huffman coding is optimal when the probability of each symbol is an integer power of ½. Arithmetic coding can allocate a fractional number of bits to each symbol so that it can approach the entropy more closely. Huffman coding and arithmetic coding have been widely used in existing image/video compression standards, e.g., JPEG, MPEG-2, H.264/AVC. The LZ or LZW utilizes a table based compression model where table entries are substituted for repeated strings of data. For most LZ methods, the table is generated dynamically from earlier input data. The dictionary based algorithm has been employed in, for example, GIF, Zip, PNG standards.
Spatial tree based approaches can be used to compress geometry data, such as random point positions and vertex positions of watertight 3D models. They organize input spatial points by an octree or a k-d tree. The tree is traversed and the information required for tree restoration is stored.
Initially, a bounding box is constructed around all points of a 3D model. The bounding box of all 3D points is regarded as a single cell in the beginning. To build the spatial tree, a cell is recursively subdivided until each non-empty cell is small enough to contain only one vertex and enable a sufficiently precise reconstruction of the vertex position. As vertex positions can be restored from central coordinates of corresponding cells, the spatial tree based algorithms may achieve multi-resolution compression with the same compression ratio as single-resolution compression algorithms.
In a k-d tree based approach, a cell is subdivided into two child cells and the number of vertices in one of the two child cells is encoded in each iteration, as shown in FIG. 1. If a parent cell contains p vertices, the number of vertices in one of the child cells can be encoded using log 2(p+1) bits with an arithmetic coder.
On the other hand, an octree based approach subdivides, in each iteration, a non-empty cell into eight child cells. For ease of illustration, 2D examples describing a quadtree are shown in FIGS. 2 and 3. The traversal orders are denoted by arrows. For encoding, a current parent cell is split into four child cells that are traversed in a pre-defined order, and a single bit per child cell indicates whether or not there is a point within the child cell. For example, in FIG. 2, the child cells of two parent cells 1 and 2 are traversed as shown in arrows, with non-empty child cells being colored gray. Child cells 210, 211, 212, and 213 of the first parent cell 1 are represented by a first sequence ‘1010’. Since the first and third child cells 210, 212 of the traversal are non-empty (i.e., contain one or more points), they are indicated by ‘2’s. The second and fourth child cells 211, 213 are empty (i.e. contain no points), they are indicated by ‘0’s. FIG. 3 shows the same cells using different traversals and resulting sequences.
FIG. 4 shows parent and child cells of an octree scheme. In the octree scheme, a parent cell is split into eight child cells 40, . . . , 46 (one hidden child cell behind lower left cell 42 is not shown). A possible traversal order could be left-right, up-down and front-back, resulting in a traversal sequence of cells 40-41-42-43-44-45-(hidden cell behind lower left cell 42)-46. Correspondingly, in the octree case the non-empty child cell configuration is denoted by 8-bit binaries, covering all the 255 possible combinations of empty and non-empty child cells. Separate encoding of the number of non-empty child cells is not required. TABLE 1 is an example of a sequence.
TABLE 1An exemplary sequence11111111011001100011101111001100. . .0001000000000010000000101000000000000001
Note that the specific traversal order of child cells within a parent cell is not very relevant for the present embodiments. In principle, any traversal order can be used for the present embodiments. In the following, the string of bits used to represent a child cell configuration is denoted as a symbol. In the example of TABLE 1, 8 bits are used for each symbol. In other implementations, the number of bits in a symbol may vary. For example, a 4-bit string is used to represent the child cell configuration for a quadtree, and thus, the number of bits for a symbol in the example of FIG. 2 is 4.
FIG. 5 shows an example of an octree structure. Each node is associated with a symbol and each layer corresponds to a certain precision of the tree representation. The initial cell is divided into eight cells. Child cells 1, 2, 5, 6, and 7 contain more vertices and child cells 3, 4, and 8 are empty, resulting an 8-bit symbol 11001110 (510) to represent the child cell configuration at layer 0. Each non-empty child cells are further divided and the corresponding child cell configurations are represented in layer 1. The subdivision may continue until each non-empty cell only contains one vertex.
The above approaches are proposed to represent vertex positions of watertight 3D models. The prediction methods may become invalid when representing random distributed points. Thus, it is preferable to employ the basic method of spatial tree to do position coding, in consideration of complexity and robustness. Take quadtree for example, the non-empty-sub-cell configuration is denoted by 4-bit binaries, covering all the 15 combinations. And the number of non-empty-child cells T is not needed any more consequently.
FIG. 6 is an exemplary diagram showing the principle of building a quadtree in prior art.
FIG. 6(a) is an exemplary diagram showing the traversal order of the quadtree construction. The traversal orders are denoted by arrows. For encoding, a current parent cell is split into four child cells that are traversed in a pre-defined order as shown in FIG. 6(a).
FIG. 6(b) is an exemplary diagram showing the hierarchical division of 2D space. As shown in FIG. 6(b), the small black squares denote the points to be coded. The plane is divided into 4 sub-cells with equal size. Since each sub-cell contains at least one points, the corresponding non-empty-sub-cell configuration is 1111. Further each sub-cell is divided into 4 sub-cells and the non-empty-sub-cell configuration is encoded. In FIG. 6(b), only the bottom-right child cell of the subcell “TL” in FIG. 2(b) contains a point. Thus, the corresponding non-empty-sub-cell configuration is 0010. The cells are iteratively subdivided and the non-empty-sub-cell configuration is encoded. The quadtree is constructed as FIG. 6(c), wherein each layer corresponds to one iteration of subdivision.
FIG. 7 is an exemplary diagram showing the flow chart of the process of building a quadtree in FIG. 6.
As shown in FIG. 7, the cell Cl,k is subdivided, wherein Cl,k denotes the kth cell at the l layer. A subdivision is terminated by the encoder when the following two conditions are met:
(a) every sub-cell at the deepest layer contains at most one point; and
(b) the distance dist(vl,k, cl,k) between the center point cl,k of the sub-cell and the point vl,k inside each sub-cell is smaller than the allowed maximal error th.
The allowed maximal error th can be set depending on the quality requirement of users.
As shown in FIG. 7, only when all the sub-cells in the layer l meet the above conditions (a) and (b), the process goes to subdivision of the next layer l+1.
The above mechanism shown in FIG. 7 works well on evenly-distributed points. However, if spatial points of a model are not evenly-distributed and some points are very close between each other, the above mechanism may have problems in coding efficiency. FIG. 8 is an exemplary diagram showing the case of unevenly-distributed points. As shown in FIG. 8, suppose the allowed maximal error of the point coordinates is 0.125, then two subdivisions are sufficient for most points except for the two points which are extremely close, represented by black squares. This is because the termination condition (a) described above cannot be satisfied for these two points. Thus, the subdivision for the other points has to be continued, result in a construction of a quadtree shown in FIG. 9. It could be appreciated that the actually nodes indicated by the broken block in FIG. 9 are useless. Therefore, the coding is inefficient for this case.